Finite-Length Analyses for Source and Channel Coding on Markov Chains

摘要

We study finite-length bounds for source coding with side information forMarkov sources and channel coding for channels with conditional Markovianadditive noise. For this purpose, we propose two criteria for finite-lengthbounds. One is the asymptotic optimality and the other is the efficientcomputability of the bound. Then, we derive finite-length upper and lowerbounds for coding length in both settings so that their computationalcomplexity is efficient. To discuss the first criterion, we derive the largedeviation bounds, the moderate deviation bounds, and second order bounds forthese two topics, and show that these finite-length bounds achieves theasymptotic optimality in these senses. For this discussion, we introduceseveral kinds of information measure for transition matrices.